package algorithm.leetcode.I1to100;

import java.util.LinkedList;
import java.util.List;

public class Q78 {

    public List<List<Integer>> subsets(int[] nums) {

        LinkedList<List<Integer>> lists = new LinkedList<>();
        LinkedList<Integer> curr = new LinkedList<>();
        back(lists, nums, 0, curr);

        return lists;
    }

    public void back(LinkedList<List<Integer>> result,
                    int[] nums,
                    int start,
                    LinkedList<Integer> curr) {
        // 终止条件
        // 正常的回溯应该在这里添加终止条件,但是本题比较特殊,根据nums是否已经遍历到头就可以自动结束

        // 添加当前解
        result.add(new LinkedList<>(curr));

        // 展开回溯
        for (int i = start; i < nums.length; i++) {
            curr.addLast(nums[i]);
            back(result, nums, i+1, curr);
            curr.removeLast();
        }
    }

    public static void main(String[] args) {
        Q78 q78 = new Q78();
        int[] ints = {1, 2, 3, 4};
        List<List<Integer>> subsets = q78.subsets(ints);
        System.out.println(subsets);
    }

}
